#include <iostream>
#include <vector>
#include <stack>

using namespace std;

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        int ret = 0;
        stack<int> st;
        for (int i = 0; i < n; i++)
        {
            while (!st.empty() && height[i] >= height[st.top()])
            {
                int bottom_h = height[st.top()];
                st.pop();
                if (st.empty()) {
                    break;
                }
                int left = st.top();
                int h = min(height[left], height[i]) - bottom_h;
                cout << h << " ";
                ret += h * (i - left - 1);
            }
            st.push(i);
        }
        return ret;
    }
};

int main()
{
    Solution s;
    vector<int> v = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
    s.trap(v);

	return 0;
}